题解 SP4318 【MFISH - Catch Fish】

发表于 | 更新于

题目大意:一条河分为$n$个段，每个段都有一个给定的鱼的数量$A_i$，现有$m$条船，每条船都有两个值$B_i$与$D_i$,$B_i$表示船必须在$B_i$处落锚，这意味着船必须占据$B_i$这个位置。且船的长度为$D_i$.数据保证$m$条船一定都可以放在河上。(也就是说我们选择时一定每条船都选，因为每条船都放显然是最优的)。求最大捕鱼数。

这道题给人一种贪心的错觉，实际上它是一个$DP$，首先对于每条船求出它左端点能放的最左边和最右边，这个结合代码应该很好理解

接下来就是$DP$了，$f_{j}$表示之前放的所有点的最右端为$j$的最大收益。显然我们可以发现每个$j$唯一对应着一条船，所以我们可以枚举每条船。

$f_{j+d_{i}-1}=max(f_{j+d_{i}-2},f_{j-1}+(sum_{a_{j+d_{i}-1}}-sum_{a_{j}}));$

在代码实现上还有一些细节需要处理，具体详见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define ll long long 
#define inf 0x3f3f3f3f
using namespace std;
struct node{
    int x,y,l,r;
}b[393939];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
void write(const int &x){
    char ggg[10001];int s=0;int tmp=x;
    if(tmp==0){putchar('0');return;}if(tmp<0){tmp=-tmp;putchar('-');}
    while(tmp>0){ggg[s++]=tmp%10+'0';tmp/=10;}while(s>0){putchar(ggg[--s]);}
}
inline bool cmp(node a,node b){
    return a.x<b.x;
}
int a[393939],f[393939];
signed main(){
    int n=read();
    for (int i=1;i<=n;++i)
        a[i]=a[i-1]+read();
    int m=read();
    for (int i=1;i<=m;++i)
        b[i].x=read(),b[i].y=read(); 
    sort(b+1,b+1+m,cmp);
    b[0].l=1;b[m+1].x=inf;
    for (int i=1;i<=m;++i)b[i].l=max(b[i].x-b[i].y+1,b[i-1].l+b[i-1].y);
    for (int i=1;i<=m;++i)b[i].r=min(b[i+1].x-b[i].y,b[i].x);
    b[m+1].r=n+1;
    for (int i=1;i<=n;++i){
        for (int j=b[i].l;j<=b[i].r;++j)
            f[j+b[i].y-1]=max(f[j+b[i].y-1],f[j-1]+a[j+b[i].y-1]-a[j-1]);
        for (int j=b[i].l+b[i].y-1;j<b[i+1].r;++j)f[j]=max(f[j],f[j-1]);
    }
    printf("%d",f[n]);
}